package com.hanxiaozhang.no10leetcode.link;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定一个链表，两两相邻节点交换。不可以修改节点中的值进行交换，只能通过交换节点完成
 * 示例1：
 * 输入：head = [1,2,3,4]
 * 输出：[2,1,4,3]
 * 示例2：
 * 输入：head = []
 * 输出：[]
 * 示例 3：
 * 输入：head = [1]
 * 输出：[1]
 * <p>
 * 思路：
 * 三步交换，不理解时，画个图就懂了
 * 举个例子：
 * 1，2，3，4四个节点，翻转2和3怎么做。首先三个指针指向1，2，3，然后断开2和3的连接，令2.next = 4，
 * 再断开3和4的连接，令3.next = 2，最后1.next = 3即可。
 *
 * @author hanxinghua
 * @create 2024/1/31
 * @since 1.0.0
 */
public class No24SwapNodesInPairs {

    public static void main(String[] args) {

        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);

        Node node = method1(head);
        LinkUtil.printLink(node);
    }



    public static Node method1(Node head) {
        // 傀儡头节点
        Node dummyHead = new Node(-1);
        dummyHead.next = head;
        Node cur = dummyHead, node1 = null, node2 = null;
        while (cur.next != null && cur.next.next != null) {

            // 当前节点后继节点
            node1 = cur.next;
            // 当前节点后继的后继节点
            node2 = cur.next.next;


            /*
             1，2，3，4四个节点，翻转2和3怎么做。首先三个指针指向1(cur)，2(node1)，3(node2)：
             -- i. 断开2和3的连接，令2.next = 4，即node1.next = node2.next；
             -- ii。再断开3和4的连接，令3.next = 2，即node2.next = node1;
             -- iii. 最后1.next = 3即可，即cur.next = node2;
             */

            // 以下三步是交换
            // 1.当前节点后继节点（node1）的后继  指向  当前节点后继的后继节点（node2）的后继
            node1.next = node2.next;
            // 2.当前节点后继的后继节点（node2）的后继 指向 当前节点的后继（node1）
            node2.next = node1;
            // 3.当前节点的后继  指向  当前节点的后继的后继
            cur.next = node2;


            // 移动到一个位置，继续处理 ，隐藏点：node1位置已经交换到当前节点的后继的后继。
            cur = node1;
        }
        return dummyHead.next;
    }
}
